11 近似最短路徑

前面介紹的所有點對最短路徑演算法，好寫的得花 n^3 的時間、比較快的又得仰賴矩陣相乘。如果是單一源頭最短路徑演算法，仰賴的 BFS 或 Dijkstra 演算法都是循序的，沒辦法輕易地平行化。如果我們對於距離的精確程度沒有太高的要求，允許一點點的誤差的話，是否有機會存在更快、或更容易平行化的演算法呢？當然是有的。

我們先來關心 APSP。這些方法大致分成兩派：一派是通過預處理，對於圖 G，找出一個子圖 H，使得 H 上面任兩點的最短距離與圖 G 上面任兩點的最短距離差不多、而且不會低估距離。這樣的子圖稱為 graph spanner (span 有著生成的意思，spanner 有點像是能生出圖中最短路徑長度的邊的集合的概念)。如果我們不限制圖 H 是圖 G 的子圖、並且允許圖 H 帶有自由設定的權重的話，這樣不低估但又生成近似最短距離的圖 H 被稱為 graph emulator (仿真圖)。

第二派是走代數路線，我們可以將圖上的點視為一種賦距空間 (metric space)、而任兩點之間的圖上距離便是它們在該空間中的距離。如果我們能夠壓縮這個賦距空間、或是將這個空間嵌入至維度更低的其他賦距空間，使得壓縮後任兩點之間的距離不失真，那麼我們便可能用更快的時間算出近似最短距離。

11.1 誤差不超過 2 的 Graph Spanner

現在讓我們來考慮以下的隨機演算法，這個方法可以幫助我們在 Õ(n^2.5) 的時間內找出一個無向無權圖中，誤差不超過 2 的不低估最短路徑。

• 輸入：無向無權圖 G
• 輸出：圖 G 的子圖 H
• 步驟：
  1. 將所有度數少於 n^{0.5} 的點，其所有相鄰邊全部加入 H。
  2. 讓每個點以 n^{-0.5} 的機率被隨機選取，令這個點集合為 S。
  3. 以 S 中的每個點為樹根，做出一棵 BFS 樹。把樹上的邊加入圖 H。
  4. 重複步驟 2 和 3，重複 log n 次。

不難發現，如果一個點度數超過 n^{0.5}，那麼有極高的機率，在某一次循環的步驟 2 之中會被加入集合 S。考慮任何一條 s 到 t 的最短路徑，如果這條路徑的邊都在 H 中，那顯然最短路徑長會被保留。如果這條路徑上某條邊沒被加入 H，那麼代表與該邊相鄰的點 v，度數很大，他旁邊很高機率會有一個點 x 被選入 S，我們此時就可以順著這個點 x 做出來的 BFS 樹一路走到 t。誤差是多少呢？注意到在圖 H 中找出來的路線為：s → v, v → x (這條邊一定存在BFS樹上，注意到這個是反向行走所以圖必須是無向圖), x → t。這條路線長度不超過 s → v, v→ x, x→ v, v → t，也就是說是原先圖 G 上面 s → t 最短路徑加上兩條邊的長度，也就是說誤差不超過 +2。

有了圖 H 以後，我們就可以對每個點做一次 BFS，找出任兩點之間的最短路徑，耗時 O(mn)，其中 m 是圖 H 的邊數。而 m 的期望值是 n^1.5 log n：因為步驟 2 每一輪會選出平均 n^0.5 個點，每個點會做出一棵帶有最多 n-1 條邊的 BFS 樹。而步驟 1 至多加入 n^1.5 條邊。
因此，我們就得到一個近似的最短距離演算法，雖然有誤差，但是時間複雜度從 n^3 降到 n^2.5 左右啦。